﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphLibrary.Algorithms
{
    sealed public class BreadthFirstSearch<TVertex, TEdge> : GraphAlgorithm<TVertex, TEdge>
        where TEdge:IEdge<TVertex>
    {
        //GraphColor.White-не обнаруженные вершины,
        //GraphColor.Gray-обнаруженные вершины,
        //GraphColor.Black-вершины, все прямые потомки которых обнаружены
        Dictionary<TVertex, GraphColor> _colours = new Dictionary<TVertex, GraphColor>();

        //вершины, доступные из исходной и их предки
        Dictionary<TVertex, TVertex> _ancestors = new Dictionary<TVertex, TVertex>();

        public BreadthFirstSearch(IGraph<TVertex,TEdge> graph)
        {
            Graph = graph;
        }

        public Dictionary<TVertex, TVertex> Ancestors
        {
            get
            {
                return _ancestors;
            }
        }

        //вершины, доступные из исходной и расстрояния в узлах до этих вершин
        Dictionary<TVertex, int> _distances = new Dictionary<TVertex, int>();

        public Dictionary<TVertex, int> Distances
        {
            get
            {
                return _distances;
            }
        }

        public void Execute(TVertex vertex)
        {
            //текущая вершина
            TVertex curr;                                                

            Queue<TVertex> q = new Queue<TVertex>();

            foreach (TVertex v1 in Graph.Vertices)
            {
                _colours.Add(v1, GraphColor.White);
            }
            _distances.Add(vertex, 0);

            q.Enqueue(vertex);
            while (q.Count != 0)
            {
                curr=q.Dequeue();
                foreach (TVertex v in Graph.AdjacentVertices(curr))
                {
                    if (_colours[v]==GraphColor.White)
                    {
                        _colours[v]=GraphColor.Gray;
                        if (_distances.ContainsKey(v))
                            _distances[v] = _distances[curr] + 1;
                        else
                            _distances.Add(v, _distances[curr] + 1);
                        _ancestors.Add(v, curr);
                        q.Enqueue(v);
                    }
                }
                _colours[curr]=GraphColor.Black;
            }
        }
    }
}
